class TreeNode:

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class CBTInserter:

    def __init__(self, root: TreeNode):
        self.root = root
        queue, self.ls = [root], []
        while queue:
            cur = queue.pop(0)
            if cur.left is None or cur.right is None:
                self.ls.append(cur)
            if cur.left is not None:
                queue.append(cur.left)
            if cur.right is not None:
                queue.append(cur.right)

    def insert(self, v: int) -> int:
        node = TreeNode(val=v)
        self.ls.append(node)
        if self.ls[0].left is None:
            self.ls[0].left = node
            return self.ls[0].val
        self.ls[0].right = node
        return self.ls.pop(0).val

    def get_root(self) -> TreeNode:
        return self.root


c = CBTInserter(TreeNode(1))
c.insert(2)

ls = [i for i in range(1, 7)]
print(ls)